/// [Power digit sum](https://projecteuler.net/problem=16)
fn main() {
    for n in &[15, 1000] {
        println!("{}:\t{}", n, power_digit_sum(n));
    }
}

fn power_digit_sum(n: &u32) -> u64 {
    let base = 10_u64.pow(15);
    let step = 2_u64.pow(10);
    let len = 20;
    let mut value = [0_u64; 20];
    if *n < 64 {
        value[0] = 2_u64.pow(*n);
    } else {
        value[0] = 2_u64.pow(63);
        let mut m = n - 63;
        while m > 10 {
            for i in 0..(len - 1) {
                value[i + 1] += value[i] / base;
                value[i] %= base;
                value[i] *= step;
            }
            value[len - 1] *= step;
            m -= 10;
        }
        let step = 2_u64.pow(m);
        for i in 0..(len - 1) {
            value[i + 1] += value[i] / base;
            value[i] %= base;
            value[i] *= step;
        }
        value[len - 1] *= step;
    }

    for i in 0..(len - 1) {
        value[i + 1] += value[i] / base;
        value[i] %= base;
    }

    let mut sum = 0_u64;
    for i in 0..len {
        let mut m = value[i];
        while m > 9 {
            sum += m % 10;
            m /= 10;
        }
        sum += m;
    }
    sum
}
